518. Coin Change 2
Medium

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

 

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

 

Constraints:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All the values of coins are unique.
  • 0 <= amount <= 5000
Accepted
200,180
Submissions
378,122
Seen this question in a real interview before?
Companies

Average Rating: 4.12 (83 votes)

Premium

Solution


Approach 1: Dynamic Programming

Template

This is a classical dynamic programming problem.

Here is a template one could use:

  • Define the base cases for which the answer is obvious.

  • Develop the strategy to compute more complex case from more simple one.

  • Link the answer to base cases with this strategy.

Example

Let's pic up an example: amount = 11, available coins - 2 cent, 5 cent and 10 cent. Note, that coins are unlimited.

fig

Base Cases: No Coins or Amount = 0

If the total amount of money is zero, there is only one combination: to take zero coins.

Another base case is no coins: zero combinations for amount > 0 and one combination for amount == 0.

fig

2 Cent Coins

Let's do one step further and consider the situation with one kind of available coins: 2 cent.

fig

It's quite evident that there could be 1 or 0 combinations here, 1 combination for even amount and 0 combinations for the odd one.

The same answer could be received in a recursive way, by computing the number of combinations for all amounts of money, from 0 to 11.

First, that's quite obvious that all amounts less than 2 are not impacted by the presence of 2 cent coins. Hence for amount = 0 and for amount = 1 one could reuse the results from the figure 2.

Starting from amount = 2, one could use 2 cent coins in the combinations. Since the amounts are considered gradually from 2 to 11, at each given moment one could be sure to add not more than one coin to the previously known combinations.

So let's pick up 2 cent coin, and use it to make up amount = 2. The number of combinations with this 2 cent coin is a number combinations for amount = 0, i.e. 1.

fig

Now let's pick up 2 cent coin, and use it to make up amount = 3. The number of combinations with this 2 cent coin is a number combinations for amount = 1, i.e. 0.

fig

That leads to DP formula for number of combinations to make up the amount = x: dp[x] = dp[x] + dp[x - coin], where coin = 2 cents is a value of coins we're currently adding.

fig

2 Cent Coins + 5 Cent Coins + 10 Cent Coins

Now let's add 5 cent coins. The formula is the same, but do not forget to add dp[x], number of combinations with 2 cent coins.

fig

The story is the same for 10 cent coins.

fig

Now the strategy is here:

  • Add coins one-by-one, starting from base case "no coins".

  • For each added coin, compute recursively the number of combinations for each amount of money from 0 to amount.

Algorithm

  • Initiate number of combinations array with the base case "no coins": dp[0] = 1, and all the rest = 0.

  • Loop over all coins:

    • For each coin, loop over all amounts from 0 to amount:

      • For each amount x, compute the number of combinations: dp[x] += dp[x - coin].
  • Return dp[amount].

Implementation

Complexity Analysis

  • Time complexity: O(N×amount)\mathcal{O}(N \times \textrm{amount}), where N is a length of coins array.

  • Space complexity: O(amount)\mathcal{O}(\textrm{amount}) to keep dp array.

Report Article Issue

Comments: 31
babhishek21's avatar
Read More

The fun part about this solution is that if you switch the order of the for loops in the code, your answer almost doubles! Learnt it the hard way.

If you're wondering why, here's a hint:

To make an amount of 3 with two coin denominations 1 and 2, you can go:
1 + 2 = 3
2 + 1 = 3
Both mean the same thing, in this question.

114
Show 9 replies
Reply
Share
Report
raju31's avatar
Read More

great article...it would be great if you guys can first explain top down approach..then bottom up

47
Show 1 reply
Reply
Share
Report
he11mean's avatar
Read More

Although the implementation looks super easy and so does the explanation neither of them is. Moreover, it is dangerously confusing. The dp relationship dp[x] = dp[x] + dp[x - coin] depends on itself, which is not permitted for dynamic programming. Optimal substructure is not shown. So this is indeed a solution, but it is not a dynamic programming one (strictly speaking at least). The problem can be solved with DP, however, for which you need a two dimensional DP array.

28
Show 3 replies
Reply
Share
Report
kevin2702's avatar
Read More

I would say the dp formula dp[x] += dp[x - coin] can be explained as
The combination of i number of coins to make change for j amount = The combination when we not using ith coin to make change for j amount + The combination when we use ith coin to make change for j amount.

It likes knapsack problem, calculate the result when we pick the current coin and not pick it and get the total

15
Show 1 reply
Reply
Share
Report
jordan34's avatar
Read More

This explanation explains how to do the problem, but doesn't fully explain how we get from the two dimensional representation to the 1D version. Or why that works. The entire explanation is two-D then suddenly we are in some optimized form.

Sadly, yet another DP explanation that's more along the lines of memorization compared to actual deep understanding. The existing explanation using the two-D was very intuitive.

12
Show 2 replies
Reply
Share
Report
egch's avatar
Read More

This video describe the problem in a great way https://www.youtube.com/watch?v=jaNZ83Q3QGc

17
Show 5 replies
Reply
Share
Report
jkrishna's avatar
Read More

nice answer

7
Reply
Share
Report
Zaizi's avatar
Read More

The corner case for this problem feels strange to me:

Wrong Answer
Your input: 0, []
Output: 0
Expected: 1

Can someone please explain why it expects to have 1 way to change coins
while coins.length = 0 && int amount = 0??

6
Show 2 replies
Reply
Share
Report
david2999999's avatar
Read More

Brute Force Recursive. TLE error

public class CoinChangeRecursiveApproach {
    public int change(int amount, int[] coins) {
        return change(amount, coins, 0);
    }

    private int change(int amount, int[] coins, int index) {
        if (amount == 0) {
            return 1;
        } else if (index >= coins.length) {
            return 0;
        }

        int combinations = 0;
        int coin = coins[index];
        int numOfCoins = 0;

        while (numOfCoins * coin <= amount) {
            combinations += change(amount - (numOfCoins * coin), coins, index + 1);
            numOfCoins++;
        }

        return combinations;
    }
}

Memoization Approach, accepted

public class CoinChangeMemoizationApproach {
    public int change(int amount, int[] coins) {
        Map<Pair, Integer> memo = new HashMap<>();
        return change(amount, coins, 0, memo);
    }

    private int change(int amount, int[] coins, int index, Map<Pair, Integer> memo) {
        if (amount == 0) {
            return 1;
        } else if (index >= coins.length) {
            return 0;
        }

        Pair key = new Pair(amount, index);

        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int combinations = 0;
        int coin = coins[index];
        int numOfCoins = 0;

        while (numOfCoins * coin <= amount) {
            combinations += change(amount - (numOfCoins * coin), coins, index + 1, memo);
            numOfCoins++;
        }

        memo.put(key, combinations);
        return combinations;
    }
}

4
Show 3 replies
Reply
Share
Report
namidairo777's avatar
Read More

DFS + backtracking can also solve it. But for large amount of inputs, it will fail due to Time Limit Exceeded 😒

7
Show 5 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/22/2021 12:32Accepted20 ms11.9 MBcpp
03/27/2021 08:37Accepted16 ms7.1 MBcpp
06/09/2020 12:47Accepted24 ms7.3 MBcpp
06/07/2020 18:47Accepted4 ms7.3 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.